#define SIZE 100


#include<stdio.h>
#include<stdlib.h>

typedef struct treeNode
{
	unsigned int data;
	struct treeNode *left;
	struct treeNode *right;
}TreeNode;

typedef struct tree
{
	TreeNode *root;
}Tree;


TreeNode *nodeFromArray(int *arr, int  size)
{
	TreeNode *ret;
	if(arr[size/2] == -1) return NULL;
	ret = malloc(sizeof(TreeNode));
	if(size==1)
	{
		if(arr[0]==-1) return NULL;
		ret->left = NULL;
		ret->right = NULL;
		ret->data = arr[0];
		return ret;
	}
	ret->data = arr[size/2];
	ret->left = nodeFromArray(arr, size/2);
	ret->right = nodeFromArray(arr + size/2 + 1, size/2);
	return ret;

}

Tree BuildTreeFromArray(int *arr, int  size)
{
	Tree ret;
	ret.root = nodeFromArray(arr, size);
	return ret;
}

void printNode(TreeNode *n)
{
	if(!n) return;
	printNode(n->left);
	printf("%d ",n->data);
	printNode(n->right);
}

void printTreeInorder(Tree tr)
{
	printNode(tr.root);
}
void freeNode(TreeNode *n)
{
	TreeNode *templ,*tempr;
	if(!n) return;
	templ = n->left;
	tempr = n->right;
	free(n);
	free(templ);
	free(tempr);
}
void freeTree(Tree tr)
{
	freeNode(tr.root);
}

int main()
{
	int size, i;
	int arr[SIZE];
	Tree tr;

	printf("Please enter the number of items: ");
	scanf("%d", &size);
	for(i=0; i<size; i++)
		scanf("%d", &arr[i]);

	tr = BuildTreeFromArray(arr, size);
	printf("The tree in inorder (LDR) format:\n");
	printTreeInorder(tr); //Print the tree in-order (LDR)
	freeTree(tr);
}
